/**
 * @author hewei
 * @version 1.0
 * @description: 306. 累加数
 * @date 2022/7/29 16:46
 */

public class IsAdditiveNumber {

    public static void main(String[] args) {
        System.out.println(new IsAdditiveNumber().isAdditiveNumber("111"));
    }

    public boolean isAdditiveNumber(String num) {
        if (num.length() < 3) return false;
        int n = num.length();
        for (int j = 1; j < n; j++) {
            if (num.charAt(0) == '0' && j != 1) break;
            for (int k = j; k < n; k++) {
                if (num.charAt(j) == '0' && k != j) break;
                String temp = stringAdd(num.substring(0, j), num.substring(j, k + 1));
                int index = k;
                String last = num.substring(j, k + 1);
                boolean flag = false;
                while (temp.length() <= n - index - 1 && temp.equals(num.substring(index + 1, index + 1 + temp.length()))) {
                    String a = temp;
                    index += temp.length();
                    temp = stringAdd(last, temp);
                    last = a;
                    flag = true;
                }
                if (index == n - 1 && flag) return true;
            }
        }
        return false;
    }

    public String stringAdd(String s1, String s2) {
        boolean flag = false;
        int m = s1.length();
        int n = s2.length();
        StringBuilder stringBuilder = new StringBuilder();
        int i = m - 1;
        int j = n - 1;
        while (i >= 0 || j >= 0) {
            char c = (char) ((i >= 0 ? s1.charAt(i) : '0') + (j >= 0 ? s2.charAt(j) : '0') - '0');
            int res;
            if (c > '9') {
                res = c - ':' + (flag ? 1 : 0);
                flag = true;
            } else if (c == '9') {
                if (flag) {
                    res = 0;
                } else res = 9;
            } else {
                res = c + (flag ? 1 : 0) - '0';
                flag = false;
            }
            stringBuilder.append(res);
            --i;
            --j;
        }
        if (flag) stringBuilder.append("1");
        return stringBuilder.reverse().toString();
    }
}
